from leetcode_test import TreeNode

"""
给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
"""


class Solutionx:
    def countNodes(self, root: TreeNode) -> int:
        """
        迭代, 没有利用完全二叉树
        """
        if not root:
            return 0
        queue = [root]
        count = 1
        while queue:
            new_queue = []
            for node in queue:
                if node.left:
                    new_queue.append(node.left)
                    count += 1
                if node.right:
                    new_queue.append(node.right)
                    count += 1

            queue = new_queue
        return count


class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        

def test():
    t = TreeNode.create([1, 2, 3, 4, 5, 6])
    assert Solution().countNodes(t) == 6


def test1():
    t = TreeNode.create([])
    assert Solution().countNodes(t) == 0


if __name__ == "__main__":
    t = TreeNode.create([])
    print(Solution().countNodes(t))
